﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DynaPrecision.Financial
{
	public static class ConvexFunctionBinarySearch
	{

		public static DynaPrecision.Pair<double, double> Search(
			Func<double, double> functor, double left, double right, int divisionCount = 10000)
		{
			DynaPrecision.Pair<double, double> result = new DynaPrecision.Pair<double, double>();
			int l = 0, r = divisionCount, m = divisionCount / 2;
			double d = (right - left) / divisionCount;
			if (divisionCount <= 1) throw new Exception();
			double ll = 0;
			double rr = 0;
			double mm = 0;
			double fl = 0;
			double fr = 0;
			double fm = 0;
			while (r - l > 2)
			{
				mm = left + m * d;
				ll = mm - d;
				rr = mm + d;
				fl = functor(ll);
				fr = functor(rr);
				fm = functor(mm);
				if (fl >= fm && fm >= fr) l = m;
				else if (fl <= fm && fm <= fr) r = m;
				else break;
				m = (l + r) / 2;
			}
			return ConvexFunctionBinarySearchResult(fl, fr, fm, ll, rr, mm);
		}
		public static DynaPrecision.Pair<double, double> ConvexFunctionBinarySearchResult(
			double l, double r, double m, double left, double right, double mid)
		{
			if (l >= m && r >= m)
			{
				return new DynaPrecision.Pair<double, double> { LeftValue = mid, RightValue = m };
			}
			else if (l >= m && m >= r)
			{
				return new DynaPrecision.Pair<double, double> { LeftValue = right, RightValue = r };
			}
			else if (l <= m && m <= r)
			{
				return new DynaPrecision.Pair<double, double> { LeftValue = left, RightValue = l };
			}
			throw new Exception();
		}
	}
}
